package com.zhaopin.theswordreferstooffer;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author yin.peide
 * @date 2021-06-11 17:32
 * 面试23: 从上往下打印二叉树
 */
public class Offer23 {

    public static void main(String[] args) {

        //初始化一棵二叉树
        TreeNode treeNode8 = new TreeNode(8);
        TreeNode treeNode6 = new TreeNode(6);
        TreeNode treeNode10 = new TreeNode(10);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode7 = new TreeNode(7);
        TreeNode treeNode9 = new TreeNode(9);
        TreeNode treeNode11 = new TreeNode(11);

        treeNode6.setLeft(treeNode5);
        treeNode6.setRight(treeNode7);

        treeNode10.setLeft(treeNode9);
        treeNode10.setRight(treeNode11);

        treeNode8.setLeft(treeNode6);
        treeNode8.setRight(treeNode10);
        List<Integer> list = breadthTraversal(treeNode8);

        for (Integer integer : list) {
            System.out.print(integer + " ");
        }
        System.out.println();

    }

    /**
     * 从上往下打印二叉树 使用队列
     */
    public static List<Integer> breadthTraversal(TreeNode treeNode) {
        List<Integer> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();


        //先插入队列
        if(null != treeNode ){
            queue.offer(treeNode);
        }else{
            return list;
        }


        while (!queue.isEmpty()) {
            TreeNode treeNode1 = queue.poll();
            list.add(treeNode1.getValue());

            if (null != treeNode1.getLeft()) {
                queue.offer(treeNode1.getLeft());
            }
            if (null != treeNode1.getRight()) {
                queue.offer(treeNode1.getRight());
            }

        }
        return list;
    }

}

